package com.peng.leetcode.backtracking;

/**
 * IsMatch
 * 给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
 *
 * '.' 匹配任意单个字符
 * '*' 匹配零个或多个前面的那一个元素
 * 所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
 *
 * 链接：https://leetcode-cn.com/problems/regular-expression-matching
 *
 * @author: lupeng6
 * @create: 2020/12/28 19:16
 */
public class IsMatch {

    public static void main(String[] args) {
//        String s = "mississippi";
//        String p = "mis*is*p*.";

        String s = "acdcb";
        String p = "a*c?b";

//        String s = "cb";
//        String p = "?a";
        System.out.println(isMatch(s, p));
    }

    public static boolean matched = false;

    public static boolean isMatch(String s, String p) {
        long start = System.currentTimeMillis();
        rMatch(s, p, 0, 0);
        System.out.println(System.currentTimeMillis() - start);
        return matched;
    }

    public static void rMatch(String s, String p, int sIndex, int pIndex) {
        if (matched) {
            return;
        }
        if (pIndex == p.length()) {
            if (s.length() == sIndex) {
                matched = true;
            }
            return;
        }
        if (p.charAt(pIndex) == '?') {
            rMatch(s, p, sIndex + 1, pIndex + 1);
        } else if (p.charAt(pIndex) == '*') {
            for (int i = 0; i < s.length() - sIndex + 1; i++) {
                rMatch(s, p, sIndex + i, pIndex + 1);
            }
        } else if (sIndex < s.length() && p.charAt(pIndex) == s.charAt(sIndex)) {
            rMatch(s, p, sIndex + 1, pIndex + 1);
        }
    }

}
